package com.dsaa.dfs;

public class _671_dfs {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        TreeNode node2 = new TreeNode(2);
        TreeNode node5 = new TreeNode(5);
        root.left = node2;
        root.right = node5;

        _671_dfs dfs = new _671_dfs();
        int secondMinimumValue = dfs.findSecondMinimumValue(root);
        System.out.println(secondMinimumValue);
    }


    public int findSecondMinimumValue(TreeNode root) {
        return dfs(root, root.val);
    }

    public int dfs(TreeNode node, int val) {
        if (node == null) {
            return -1;
        }
        if (node.val > val) {
            return val;
        }
        int left = dfs(node.left, val);
        int right = dfs(node.right, val);
        if (left >= 0 && right >= 0) {
            return Math.min(left, right);
        }
        return Math.max(left, right);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
